package offer.offer01;

/**
 *
 */
public class S13机器人运动范围 {
    /**
     * 86 dfs + 二维数组遍历。
     */
    private int count = 0;
    private int target;
    public int movingCount(int m, int n, int k) {
        if(m == 0 || n == 0 || k < 0) return 0;
        int[][] matrix = new int[m][n];
        this.target = k;
        movingCountHelp(matrix, 0, 0);
        return this.count;
    }
    // 这里把对条件是否符合的判断塞到函数开头, 那么在函数结尾就可以放心递归了,
    // 以前在递归的时候判断是否可以往下递归, 其实多了很多代码。
    public void movingCountHelp(int[][] matrix, int row, int col){
        // System.out.println("" + row + " " + col + " " + divSum(row, col));
        if(row < 0 || row >= matrix.length || col < 0 || col >= matrix[0].length
                || matrix[row][col] == 1 ||divSum(row, col) > target)
            return;

        this.count ++;
        matrix[row][col] = 1;
        movingCountHelp(matrix, row, col - 1);
        movingCountHelp(matrix, row, col + 1);
        movingCountHelp(matrix, row + 1, col);
        movingCountHelp(matrix, row - 1, col);

    }
    public int divSum(int row, int col){
        return row / 100 + (row % 100) / 10 + (row % 10) + col / 100 + (col % 100) / 10 + (col % 10);
    }

    /**
     * 别人的, 递推方法, 即如果这个点的位置和符合条件, 那么如果他的上面和左边有可达的点, 那么他也是可达的。
     * 我们自上到下, 自左到右, 每个点只需要访问一次就行。
     */
    public int movingCount2(int m, int n, int k) {
        if (k == 0) {
            return 1;
        }
        boolean[][] vis = new boolean[m][n];
        int ans = 1;
        vis[0][0] = true;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if ((i == 0 && j == 0) || get(i) + get(j) > k) {
                    continue;
                }
                // 边界判断
                if (i - 1 >= 0) {
                    vis[i][j] |= vis[i - 1][j];
                }
                if (j - 1 >= 0) {
                    vis[i][j] |= vis[i][j - 1];
                }
                ans += vis[i][j] ? 1 : 0;
            }
        }
        return ans;
    }

    // 建议参考一下这个获得每一位和的办法, 我总是喜欢从高位开始计算, 其实从低位开始加更加方便。
    private int get(int x) {
        int res = 0;
        while (x != 0) {
            res += x % 10;
            x /= 10;
        }
        return res;
    }
}
